package com.ds.map_set;

import java.util.NoSuchElementException;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: TODO
 * @date 2022/10/17 21:53
 */
public class MyHashMap {
    // 有效节点个数
    private int size;
    // 实际存储元素的Node数组
    private Node[] hashTable;
    // 取模数
    private int M;
    // 负载因子
    private static final double LOAD_FACTOR = 0.75;

    public MyHashMap() {
        this(16);
    }

    public MyHashMap(int init) {
        this.hashTable = new Node[init];
        this.M = init;
    }

    /**
     * 对key求哈希
     * @param key
     * @return
     */
    public int hash(int key) {
        return Math.abs(key) % M;
    }

    /**
     * 将一对键值对保存到当前hash表中
     * @param key
     * @param val
     * @return 若key存在，此时修改原来键值对，返回修改前的元素
     */
    public int put(int key,int val) {
        // 1.先对key取模
        int index = hash(key);
        // 2.遍历这个index对应链表，查看key是否存在
        for (Node x = hashTable[index];x != null;x = x.next) {
            if (x.key == key) {
                int oldVal = x.value;
                x.value = val;
                return oldVal;
            }
        }
        // 3.此时整个链表中不包含相应key的结点，头插到当前位置
        Node node = new Node(key,val);
        // 头结点 hashTable[index]
        node.next = hashTable[index];
        hashTable[index] = node;
        size ++;
        // 添加元素之后判断是否需要扩容
        if (size >= hashTable.length * LOAD_FACTOR) {
            resize();
        }
        return val;
    }

    /**
     * 判断当前key是否在表中存在
     * @param key
     * @return
     */
    public boolean containsKey(int key) {
        int index = hash(key);
        for (Node x = hashTable[index];x != null;x = x.next) {
            if (x.key == key) {
                return true;
            }
        }
        return false;
    }
    /**
     * 判断value是否存在
     * @param value
     * @return
     */
    public boolean containsValue(int value) {
        // 全表扫描
        for (int i = 0; i < hashTable.length; i++) {
            for (Node x = hashTable[i];x != null;x = x.next) {
                if (x.value == value) {
                    return true;
                }
            }
        }
        return false;
    }

    // TODO 判断(key,value)存在

    /**
     * 在哈希表中删除指定的键值对(key,value)
     * @param key
     * @param value
     * @return
     */
    public boolean remove(int key,int value) {
        int index = hash(key);
        // 判断头节点是否是待删除节点
        Node head = hashTable[index];
        if (head.key == key && head.value == value) {
            // 此时头节点就是待删除节点
            hashTable[index] = head.next;
            head = head.next = null;
            size --;
            return true;
        }
        Node prev = head;
        while (prev.next != null) {
            if (prev.next.key == key && prev.next.value == value) {
                // prev恰好是待删除节点的前驱
                Node cur = prev.next;
                prev.next = cur.next;
                cur = cur.next = null;
                size --;
                return true;
            }else {
                prev = prev.next;
            }
        }
        // 哈希表没有这个节点
        throw new NoSuchElementException("no such node!!remove error");
    }


    /**
     * 哈希表的扩容方法，新数组的长度变为原来的一倍
     */
    private void resize() {
        // 1.产生一个新数组且新数组长度变为原来的一倍
        Node[] newTable = new Node[hashTable.length << 1];
        // 2.进行元素的搬移操作，将原数组中的所有元素搬移到新数组中,
        // 此时取模数变为新数组的长度
        this.M = newTable.length;
        // 3.进行元素搬移
        for (int i = 0; i < hashTable.length; i++) {
            for (Node x = hashTable[i];x != null;) {
                Node next = x.next;
                // 将x搬移到新数组的位置
                int index = hash(x.key);
                // 新数组头插
                x.next = newTable[index];
                newTable[index] = x;
                // 继续搬移原数组的后继节点
                x = next;
            }
        }
        hashTable = newTable;
    }
}

// 当前哈希表中保存的结点，key = value的键值对对象
class Node {
    // 对key进行hash运算
    int key;
    int value;
    // 下一个节点地址
    Node next;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}
